<!DOCTYPE html>
<html lang="en">
    <!-- title -->


    

<!-- keywords -->



<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="author" content="Coder XiaoLiu">
    <meta name="renderer" content="webkit">
    <meta name="copyright" content="Coder XiaoLiu">
    
        <meta name="keywords" content="hexo,spring,java">
    
    <meta name="description" content="">
    <meta name="description" content="问题描述 你将会获得一系列视频片段，这些片段来自于一项持续时长为time秒的体育赛事。这些片段可能有所重叠，也可能长度不一。使用数组clips描述所有的视频片段，其中clips[i] &#x3D; [starti, endi&gt;]&gt;表示；某些视频片段开始于starti并于endi结束。">
<meta property="og:type" content="article">
<meta property="og:title" content="LeetCode.1024.视频拼接">
<meta property="og:url" content="https://mnjic.gitee.io/2022/05/05/1024.VideoStitching/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="问题描述 你将会获得一系列视频片段，这些片段来自于一项持续时长为time秒的体育赛事。这些片段可能有所重叠，也可能长度不一。使用数组clips描述所有的视频片段，其中clips[i] &#x3D; [starti, endi&gt;]&gt;表示；某些视频片段开始于starti并于endi结束。">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://mnjic.gitee.io/2022/05/05/1024.VideoStitching/video_type_1.png">
<meta property="og:image" content="https://mnjic.gitee.io/2022/05/05/1024.VideoStitching/video_type_2.png">
<meta property="og:image" content="https://mnjic.gitee.io/2022/05/05/1024.VideoStitching/video_type_3.png">
<meta property="article:published_time" content="2022-05-05T12:29:11.000Z">
<meta property="article:modified_time" content="2022-05-06T12:38:48.195Z">
<meta property="article:author" content="Coder XiaoLiu">
<meta property="article:tag" content="LeetCode">
<meta property="article:tag" content="动态规划">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://mnjic.gitee.io/2022/05/05/1024.VideoStitching/video_type_1.png">
    <meta http-equiv="Cache-control" content="no-cache">
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
    <link rel="icon" href="/assets/favicon.ico">
    
    <title>LeetCode.1024.视频拼接 · XiaoLiu&#39;s Studio</title>
    <!-- /*! loadCSS. [c]2017 Filament Group, Inc. MIT License */
/* This file is meant as a standalone workflow for
- testing support for link[rel=preload]
- enabling async CSS loading in browsers that do not support rel=preload
- applying rel preload css once loaded, whether supported or not.
*/ -->
<script>
    (function (w) {
        'use strict'
        // rel=preload support test
        if (!w.loadCSS) {
            w.loadCSS = function () {}
        }
        // define on the loadCSS obj
        var rp = (loadCSS.relpreload = {})
        // rel=preload feature support test
        // runs once and returns a function for compat purposes
        rp.support = (function () {
            var ret
            try {
                ret = w.document.createElement('link').relList.supports('preload')
            } catch (e) {
                ret = false
            }
            return function () {
                return ret
            }
        })()

        // if preload isn't supported, get an asynchronous load by using a non-matching media attribute
        // then change that media back to its intended value on load
        rp.bindMediaToggle = function (link) {
            // remember existing media attr for ultimate state, or default to 'all'
            var finalMedia = link.media || 'all'

            function enableStylesheet() {
                link.media = finalMedia
            }

            // bind load handlers to enable media
            if (link.addEventListener) {
                link.addEventListener('load', enableStylesheet)
            } else if (link.attachEvent) {
                link.attachEvent('onload', enableStylesheet)
            }

            // Set rel and non-applicable media type to start an async request
            // note: timeout allows this to happen async to let rendering continue in IE
            setTimeout(function () {
                link.rel = 'stylesheet'
                link.media = 'only x'
            })
            // also enable media after 3 seconds,
            // which will catch very old browsers (android 2.x, old firefox) that don't support onload on link
            setTimeout(enableStylesheet, 3000)
        }

        // loop through link elements in DOM
        rp.poly = function () {
            // double check this to prevent external calls from running
            if (rp.support()) {
                return
            }
            var links = w.document.getElementsByTagName('link')
            for (var i = 0; i < links.length; i++) {
                var link = links[i]
                // qualify links to those with rel=preload and as=style attrs
                if (
                    link.rel === 'preload' &&
                    link.getAttribute('as') === 'style' &&
                    !link.getAttribute('data-loadcss')
                ) {
                    // prevent rerunning on link
                    link.setAttribute('data-loadcss', true)
                    // bind listeners to toggle media back
                    rp.bindMediaToggle(link)
                }
            }
        }

        // if unsupported, run the polyfill
        if (!rp.support()) {
            // run once at least
            rp.poly()

            // rerun poly on an interval until onload
            var run = w.setInterval(rp.poly, 500)
            if (w.addEventListener) {
                w.addEventListener('load', function () {
                    rp.poly()
                    w.clearInterval(run)
                })
            } else if (w.attachEvent) {
                w.attachEvent('onload', function () {
                    rp.poly()
                    w.clearInterval(run)
                })
            }
        }

        // commonjs
        if (typeof exports !== 'undefined') {
            exports.loadCSS = loadCSS
        } else {
            w.loadCSS = loadCSS
        }
    })(typeof global !== 'undefined' ? global : this)
</script>

    <style type="text/css">
    @font-face {
        font-family: 'Oswald-Regular';
        src: url("/font/Oswald-Regular.ttf");
    }

    body {
        margin: 0;
    }

    header,
    footer,
    .back-top,
    .sidebar,
    .container,
    .site-intro-meta,
    .toc-wrapper {
        display: none;
    }

    .site-intro {
        position: relative;
        z-index: 3;
        width: 100%;
        /* height: 50vh; */
        overflow: hidden;
    }

    .site-intro-placeholder {
        position: absolute;
        z-index: -2;
        top: 0;
        left: 0;
        width: calc(100% + 300px);
        height: 100%;
        background: repeating-linear-gradient(-45deg, #444 0, #444 80px, #333 80px, #333 160px);
        background-position: center center;
        transform: translate3d(-226px, 0, 0);
        animation: gradient-move 2.5s ease-out 0s infinite;
    }

    @keyframes gradient-move {
        0% {
            transform: translate3d(-226px, 0, 0);
        }
        100% {
            transform: translate3d(0, 0, 0);
        }
    }
</style>

    <link rel="preload" href="/css/style.css?v=20211217" as="style" onload="this.onload=null;this.rel='stylesheet'">
    <link rel="preload" href="/css/dark.css?v=20211217" as="style">
    <link rel="stylesheet" href="/css/dark.css">
    <link rel="stylesheet" href="/css/mobile.css?v=20211217" media="(max-width: 960px)">
    <link rel="preload" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css" as="style" onload="this.onload=null;this.rel='stylesheet'">
    <link rel="preload" href="https://cdn.jsdelivr.net/npm/jquery@3.6.0/dist/jquery.min.js" as="script">
    <link rel="preload" href="/scripts/main.js?v=20211217" as="script">
    <link rel="preload" href="/scripts/dark.js?v=20211217" as="script">
    <link rel="preload" href="/font/Oswald-Regular.ttf" as="font" crossorigin>
    <link rel="preload" href="https://at.alicdn.com/t/font_327081_1dta1rlogw17zaor.woff" as="font" crossorigin>
    <!-- algolia -->
    
    <!-- 百度统计  -->
    
    <!-- 谷歌统计  -->
    
<meta name="generator" content="Hexo 5.4.0"></head>

    <script src="https://cdn.jsdelivr.net/npm/jquery@3.6.0/dist/jquery.min.js"></script>
    <script type="text/javascript">
        if (typeof window.$ == undefined) {
            console.warn('jquery load from jsdelivr failed, will load local script')
            document.write('<script src="/lib/jquery.min.js" />')
        }
    </script>
    
        <body class="post-body">
    
        <!-- header -->
        <header class="header header-mobile">
    <!-- top read progress line -->
    <div class="header-element">
        <div class="read-progress"></div>
    </div>
    <!-- sidebar menu button -->
    <div class="header-element">
        
            <div class="header-sidebar-menu">
        
            
                <div style="padding-left: 1px;">&#xe775;</div>
            
        </div>
    </div>
    <!-- header actions -->
    <div class="header-actions">
        <!-- theme mode switch button -->
        <span class="header-theme-btn header-element">
            <i class="fas fa-adjust"></i>
        </span>
        <!-- back to home page text -->
        <span class="home-link header-element">
            <a href=/>XiaoLiu's Studio</a>
        </span>
    </div>
    <!-- toggle banner for post layout -->
    
        
            <div class="banner">
        
            <div class="blog-title header-element">
                <a href="/">XiaoLiu&#39;s Studio</a>
            </div>
            <div class="post-title header-element">
                <a href="#" class="post-name">LeetCode.1024.视频拼接</a>
            </div>
        </div>
    
</header>

        <!-- fixed footer -->
        <footer class="footer-fixed">
    <!-- back to top button -->
    <div class="footer-fixed-element">
        
            <div class="back-top back-top-hidden">
        
        
            <div>&#xe639;</div>
        
        </div>
    </div>
</footer>

        <!-- wrapper -->
        <div class="wrapper">
            <div class="site-intro" style="







    height:50vh;

">
    
    <!-- 主页  -->
    
        
    <!-- 404页  -->
            
    <div class="site-intro-placeholder"></div>
    <div class="site-intro-img" style="background-image: url(/intro/post-bg.jpg)"></div>
    <div class="site-intro-meta">
        <!-- 标题  -->
        <h1 class="intro-title">
            <!-- 主页  -->
            
                LeetCode.1024.视频拼接
            <!-- 404 -->
            
        </h1>
        <!-- 副标题 -->
        <p class="intro-subtitle">
            <!-- 主页副标题  -->
            
                
            <!-- 404 -->
            
        </p>
        <!-- 文章页 meta -->
        
            <div class="post-intros">
                <!-- 文章页标签  -->
                
                    <div class= post-intro-tags >
    
    
        <a class="post-tag" href="javascript:void(0);" data-tags="LeetCode">LeetCode</a>
    
        <a class="post-tag" href="javascript:void(0);" data-tags="动态规划">动态规划</a>
    
</div>

                
                
                    <div class="post-intro-read">
                        <span>Word count: <span class="post-count word-count">1.3k</span>Reading time: <span class="post-count reading-time">5 min</span></span>
                    </div>
                
                <div class="post-intro-meta">
                    <!-- 撰写日期 -->
                    <span class="iconfont-archer post-intro-calander">&#xe676;</span>
                    <span class="post-intro-time">2022/05/05</span>
                    <!-- busuanzi -->
                    
                        <span id="busuanzi_container_page_pv" class="busuanzi-pv">
                            <span class="iconfont-archer post-intro-busuanzi">&#xe602;</span>
                            <span id="busuanzi_value_page_pv"></span>
                        </span>
                    
                    <!-- 文章分享 -->
                    <span class="share-wrapper">
                        <span class="iconfont-archer share-icon">&#xe71d;</span>
                        <span class="share-text">Share</span>
                        <ul class="share-list">
                            <li class="iconfont-archer share-qr" data-type="qr">&#xe75b;
                                <div class="share-qrcode"></div>
                            </li>
                            <li class="iconfont-archer" data-type="weibo">&#xe619;</li>
                            <li class="iconfont-archer" data-type="qzone">&#xe62e;</li>
                            <li class="iconfont-archer" data-type="twitter">&#xe634;</li>
                            <li class="iconfont-archer" data-type="facebook">&#xe67a;</li>
                        </ul>
                    </span>
                </div>
            </div>
        
    </div>
</div>

            <script>
  // get user agent
  function getBrowserVersions() {
    var u = window.navigator.userAgent
    return {
      userAgent: u,
      trident: u.indexOf('Trident') > -1, //IE内核
      presto: u.indexOf('Presto') > -1, //opera内核
      webKit: u.indexOf('AppleWebKit') > -1, //苹果、谷歌内核
      gecko: u.indexOf('Gecko') > -1 && u.indexOf('KHTML') == -1, //火狐内核
      mobile: !!u.match(/AppleWebKit.*Mobile.*/), //是否为移动终端
      ios: !!u.match(/\(i[^;]+;( U;)? CPU.+Mac OS X/), //ios终端
      android: u.indexOf('Android') > -1 || u.indexOf('Linux') > -1, //android终端或者uc浏览器
      iPhone: u.indexOf('iPhone') > -1 || u.indexOf('Mac') > -1, //是否为iPhone或者安卓QQ浏览器
      iPad: u.indexOf('iPad') > -1, //是否为iPad
      webApp: u.indexOf('Safari') == -1, //是否为web应用程序，没有头部与底部
      weixin: u.indexOf('MicroMessenger') == -1, //是否为微信浏览器
      uc: u.indexOf('UCBrowser') > -1, //是否为android下的UC浏览器
    }
  }
  var browser = {
    versions: getBrowserVersions(),
  }
  console.log('userAgent: ' + browser.versions.userAgent)

  // callback
  function fontLoaded() {
    console.log('font loaded')
    if (document.getElementsByClassName('site-intro-meta')) {
      document
        .getElementsByClassName('intro-title')[0]
        .classList.add('intro-fade-in')
      document
        .getElementsByClassName('intro-subtitle')[0]
        .classList.add('intro-fade-in')
      var postIntros = document.getElementsByClassName('post-intros')[0]
      if (postIntros) {
        postIntros.classList.add('post-fade-in')
      }
    }
  }

  // UC不支持跨域，所以直接显示
  function asyncCb() {
    if (browser.versions.uc) {
      console.log('UCBrowser')
      fontLoaded()
    } else {
      WebFont.load({
        custom: {
          families: ['Oswald-Regular'],
        },
        loading: function () {
          // 所有字体开始加载
          // console.log('font loading');
        },
        active: function () {
          // 所有字体已渲染
          fontLoaded()
        },
        inactive: function () {
          // 字体预加载失败，无效字体或浏览器不支持加载
          console.log('inactive: timeout')
          fontLoaded()
        },
        timeout: 5000, // Set the timeout to two seconds
      })
    }
  }

  function asyncErr() {
    console.warn('script load from CDN failed, will load local script')
  }

  // load webfont-loader async, and add callback function
  function async(u, cb, err) {
    var d = document,
      t = 'script',
      o = d.createElement(t),
      s = d.getElementsByTagName(t)[0]
    o.src = u
    if (cb) {
      o.addEventListener(
        'load',
        function (e) {
          cb(null, e)
        },
        false
      )
    }
    if (err) {
      o.addEventListener(
        'error',
        function (e) {
          err(null, e)
        },
        false
      )
    }
    s.parentNode.insertBefore(o, s)
  }

  var asyncLoadWithFallBack = function (arr, success, reject) {
    var currReject = function () {
      reject()
      arr.shift()
      if (arr.length) async(arr[0], success, currReject)
    }

    async(arr[0], success, currReject)
  }

  asyncLoadWithFallBack(
    [
      'https://cdn.jsdelivr.net/npm/webfontloader@1.6.28/webfontloader.min.js',
      'https://cdn.bootcss.com/webfont/1.6.28/webfontloader.js',
      "/lib/webfontloader.min.js",
    ],
    asyncCb,
    asyncErr
  )
</script>

            <img class="loading" src="/assets/loading.svg" style="display: block; margin: 6rem auto 0 auto; width: 6rem; height: 6rem;" />
            <div class="container container-unloaded">
                <main class="main post-page">
    <article class="article-entry">
        <h2 id="问题描述">问题描述</h2>
<p>你将会获得一系列视频片段，这些片段来自于一项持续时长为<code>time</code>秒的体育赛事。这些片段可能有所重叠，也可能长度不一。使用数组<code>clips</code>描述所有的视频片段，其中<code>clips[i]
= [start<sub>i</sub>,
end<sub>i</sub>&gt;]</code>&gt;表示；某些视频片段开始于<code>start<sub>i</sub></code>并于<code>end<sub>i</sub></code>结束。</p>
<span id="more"></span>
<p>甚至可以对这些片段自由地进行再剪辑：</p>
<ul>
<li>例如，片段<code>[0, 7]</code>可以剪切成<code>[0, 1] + [1, 3] + [3, 7]</code>三部分。</li>
</ul>
<p>我们需要对这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段<code>([0, time])</code>。返回所需要片段的最小数目，如果无法完成，则返回<code>-1</code>。</p>
<p><strong>示例1：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10</span><br><span class="line">输出：3</span><br><span class="line">解释：</span><br><span class="line">选中 [0,2], [8,10], [1,9] 这三个片段。</span><br><span class="line">然后，按下面的方案重制比赛片段：</span><br><span class="line">将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。</span><br><span class="line">现在手上的片段为 [0,2] + [2,8] + [8,10]，而这些覆盖了整场比赛 [0, 10]。</span><br></pre></td></tr></table></figure>
<p><strong>示例2：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">输入：clips = [[0,1],[1,2]], time = 5</span><br><span class="line">输出：-1</span><br><span class="line">解释：</span><br><span class="line">无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。</span><br></pre></td></tr></table></figure>
<p><strong>示例3：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9</span><br><span class="line">输出：3</span><br><span class="line">解释： </span><br><span class="line">选取片段 [0,4], [4,7] 和 [6,9] 。</span><br></pre></td></tr></table></figure>
<h2 id="问题求解方法及复杂度分析">问题求解方法及复杂度分析</h2>
<ul>
<li><p><strong>问题求解方法</strong></p>
<p>本题要求返回覆盖时长为<code>Time</code>的某个体育赛事的最少片段，属于求最值的问题，我们可以运用动态规划的思想来进行求解。我们定义`<code>dp[Time + 1]</code>数组，用来定义覆盖当前体育赛事所需要的最少视频片段。<code>dp[i]</code>表示覆盖区间<code>[0, i]</code>最少的视频片段数，那么本题最后的结果就是求<code>dp[Time]</code>。</p>
<ul>
<li><p>初始状态：我们需要求覆盖每个时刻的最少视频片段，就必定会涉及比较，因此我们要对<code>dp[Time + 1]</code>数组设置一个比较大的值<code>MAX_VALUE</code>，以保证我们每次求得的是当前所需要视频片段的最小值。单独规定<code>dp[0] = 0</code>。因为<code>[0, 0]</code>是空区间，我们最多需要0个视频片段就可以覆盖。</p></li>
<li><p>状态转移方程</p>
<p>求<code>dp[i]</code>时，对于每个遍历的<code>clips[j]</code>我们都会分为一下三种情况</p>
<ol type="1">
<li><p>当前<code>clips[j]</code>覆盖不了<code>[0,
start<sub>j</sub>]</code>，也覆盖不了<code>[0, i]</code>，当前我们不做任何操作，即保持<code>dp[i]</code>的初始值<code>MAX_VALUE</code>，最后我们对于结果为<code>MAX_VALUE</code>我们都认为是无法覆盖的，返回<code>-1</code>。</p>
<img src="/2022/05/05/1024.VideoStitching/video_type_1.png" class="" title="clips[i]情况1"></li>
<li><p><code>[0,
start<sub>j</sub>]</code>已经被覆盖，但是要覆盖<code>[0, i]</code>区间还需要加上<code>clips[j]</code>所在的部分片段。我们将前半部分保留<code>[0,
start<sub>j</sub>]</code>，
前半部分所需要的视频片段数为<code>dp[start]</code>，因此我们要覆盖<code>[0, i]</code>部分，需要的视频片段数为<code>dp[start] + 1</code>，因此，<code>dp[i] = dp[start]  + 1</code>。</p>
<img src="/2022/05/05/1024.VideoStitching/video_type_2.png" class="" title="clips[i]情况2"></li>
<li><p><code>[0, i]</code>区间已经被覆盖，我们需要计算<code>dp[i] = min&#123;dp[i], dp[start] + 1&#125;</code>。</p>
<img src="/2022/05/05/1024.VideoStitching/video_type_3.png" class="" title="clips[i]情况3"></li>
</ol>
<p>综合上述三种情况，我们得出状态转移方程：<code>dp[i] = min&#123;dp[i], dp[start] + 1&#125;</code></p></li>
</ul></li>
<li><p><strong>复杂度分析</strong></p>
<ul>
<li>时间复杂度：<code>O(Time*n )</code>，其中Time是体育赛事时长（区间长度），n是视频片段的数量。</li>
<li>空间复杂度：<code>O(Time)</code>，
其中Time是体育赛事时长（区间长度）。</li>
</ul></li>
</ul>
<h2 id="代码示例">代码示例</h2>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">videoStitching</span><span class="params">(<span class="keyword">int</span>[][] clips, <span class="keyword">int</span> time)</span></span>&#123;</span><br><span class="line"> 	<span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[time + <span class="number">1</span>];</span><br><span class="line">	Arrays.fill(dp, Integer.MAX_VALUE);</span><br><span class="line"> 	dp[<span class="number">0</span>] = <span class="number">0</span>; <span class="comment">//覆盖[0,0]是空区间，所以为 0</span></span><br><span class="line"> 	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= time; i++) &#123;</span><br><span class="line"> 		<span class="keyword">for</span> (<span class="keyword">int</span>[] clip : clips) &#123;</span><br><span class="line"> 			<span class="keyword">if</span> ((clip[START] &lt; i) &amp;&amp; (clip[END] &gt;= i)) &#123;</span><br><span class="line"> 				dp[i] = Math.min(dp[i], (dp[clip[START]] + <span class="number">1</span>));</span><br><span class="line"> 			&#125;</span><br><span class="line"> 		&#125;</span><br><span class="line"> 	&#125;</span><br><span class="line"> 	<span class="keyword">return</span> dp[time] == Integer.MAX_VALUE ? -<span class="number">1</span> : dp[time];</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure>
<h2 id="总结">总结</h2>
<p><strong>动态规划解题的步骤：</strong></p>
<ol type="1">
<li>划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，
注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。</li>
<li>确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状
态表示出来。当然，状态的选择要满足无后效性。</li>
<li>确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就
是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也
就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法
和状态转移方程。</li>
<li>寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。</li>
</ol>

    </article>
    <!-- license -->
    
        <div class="license-wrapper">
            <p>Author：<a href="https://mnjic.gitee.io">Coder XiaoLiu</a>
            <p>Link：<a href="https://mnjic.gitee.io/2022/05/05/1024.VideoStitching/">https://mnjic.gitee.io/2022/05/05/1024.VideoStitching/</a>
            <p>Publish date：<a href="https://mnjic.gitee.io/2022/05/05/1024.VideoStitching/">May 5th 2022, 8:29:11 pm</a>
            <p>Update date：<a href="https://mnjic.gitee.io/2022/05/05/1024.VideoStitching/">May 6th 2022, 8:38:48 pm</a>
            <p>License：本文采用<a rel="license noopener" target="_blank" href="http://creativecommons.org/licenses/by-nc/4.0/">知识共享署名-非商业性使用 4.0 国际许可协议</a>进行许可</p>
        </div>
    
    <!-- paginator -->
    <ul class="post-paginator">
        <li class="next">
            
                <div class="nextSlogan">Next Post</div>
                <a href="/2022/05/06/11.ContainerWithMostWater/" title="LeetCode.11.盛水最多的容器">
                    <div class="nextTitle">LeetCode.11.盛水最多的容器</div>
                </a>
            
        </li>
        <li class="previous">
            
                <div class="prevSlogan">Previous Post</div>
                <a href="/2022/05/05/23.Merge%20k%20Sorted%20Lists/" title="LeetCode.23.合并K个链表">
                    <div class="prevTitle">LeetCode.23.合并K个链表</div>
                </a>
            
        </li>
    </ul>
    <!-- comment -->
    
        <div class="post-comment">
            <!-- 来必力 City 版安装代码 -->


            

            

            

            <!-- utteranc评论 -->


            <!-- partial('_partial/comment/changyan') -->
            <!--PC版-->


            
            

            

        </div>
    
    <!-- timeliness note -->
    <!-- idea from: https://hexo.fluid-dev.com/posts/hexo-injector/#%E6%96%87%E7%AB%A0%E6%97%B6%E6%95%88%E6%80%A7%E6%8F%90%E7%A4%BA -->
    
    <!-- Mathjax -->
    
        
    <script>
        MathJax = {
            tex: {
                inlineMath: [['$', '$'], ['\\(', '\\)']],
                skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
            }
        };
    </script>

    <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
    <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3.2.0/es5/tex-mml-chtml.js"></script>


    
</main>

                <!-- profile -->
                
            </div>
            <footer class="footer footer-unloaded">
    <!-- social  -->
    
        <div class="social">
            
    
        
            
                <a href="mailto:269810721@qq.com" class="iconfont-archer email" title=email ></a>
            
        
    
        
            
                <a href="//github.com/mnjic-503" class="iconfont-archer github" target="_blank" title=github></a>
            
        
    
        
            
                <span class="iconfont-archer wechat" title=wechat>
                    
                    <img class="profile-qr" src="/assets/weichat_qrcode.jpg" />
                </span>
            
        
    
        
            
                <span class="iconfont-archer qq" title=qq>
                    
                    <img class="profile-qr" src="/assets/QQ_qrcode.jpg" />
                </span>
            
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    
        
    


        </div>
    
    <!-- powered by Hexo  -->
    <div class="copyright">
        <span id="hexo-power">Powered by <a href="https://hexo.io/" target="_blank">Hexo</a></span><span class="iconfont-archer power">&#xe635;</span><span id="theme-info">theme <a href="https://github.com/fi3ework/hexo-theme-archer" target="_blank">Archer</a></span>
    </div>
    <!-- website approve for Chinese user -->
    
    <!-- 不蒜子  -->
    
        <div class="busuanzi-container">
            
             
                <span id="busuanzi_container_site_pv">PV: <span id="busuanzi_value_site_pv"></span> :)</span>
            
        </div>
    	
</footer>

        </div>
        <!-- toc -->
        
            <div class="toc-wrapper toc-wrapper-loding" style=







    top:50vh;

>
                <div class="toc-catalog">
                    <span class="iconfont-archer catalog-icon">&#xe613;</span><span>CATALOG</span>
                </div>
                <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%97%AE%E9%A2%98%E6%8F%8F%E8%BF%B0"><span class="toc-number">1.</span> <span class="toc-text">问题描述</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3%E6%96%B9%E6%B3%95%E5%8F%8A%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">2.</span> <span class="toc-text">问题求解方法及复杂度分析</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E7%A4%BA%E4%BE%8B"><span class="toc-number">3.</span> <span class="toc-text">代码示例</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%BB%E7%BB%93"><span class="toc-number">4.</span> <span class="toc-text">总结</span></a></li></ol>
            </div>
        
        <!-- sidebar -->
        <div class="sidebar sidebar-hide">
    <ul class="sidebar-tabs sidebar-tabs-active-0">
        <li class="sidebar-tab-archives"><span class="iconfont-archer">&#xe67d;</span><span class="tab-name">Archive</span></li>
        <li class="sidebar-tab-tags"><span class="iconfont-archer">&#xe61b;</span><span class="tab-name">Tag</span></li>
        <li class="sidebar-tab-categories"><span class="iconfont-archer">&#xe666;</span><span class="tab-name">Cate</span></li>
    </ul>
    <div class="sidebar-content sidebar-content-show-archive">
        <div class="sidebar-panel-archives">
    <!-- 在 ejs 中将 archive 按照时间排序 -->
    
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    
    
    
    
    <div class="total-and-search">
        <div class="total-archive">
        Total : 11
        </div>
        <!-- search  -->
        
    </div>
    
    <div class="post-archive">
    
        
            
            
            <div class="archive-year"> 2022 </div>
            <ul class="year-list">
            
        
        <li class="archive-post-item">
            <span class="archive-post-date">05/06</span>
            <a class="archive-post-title" href="/2022/05/06/11.ContainerWithMostWater/">LeetCode.11.盛水最多的容器</a>
        </li>
    
        
        <li class="archive-post-item">
            <span class="archive-post-date">05/05</span>
            <a class="archive-post-title" href="/2022/05/05/1024.VideoStitching/">LeetCode.1024.视频拼接</a>
        </li>
    
        
        <li class="archive-post-item">
            <span class="archive-post-date">05/05</span>
            <a class="archive-post-title" href="/2022/05/05/23.Merge%20k%20Sorted%20Lists/">LeetCode.23.合并K个链表</a>
        </li>
    
        
            
            
                
                </ul>
            
            <div class="archive-year"> 2021 </div>
            <ul class="year-list">
            
        
        <li class="archive-post-item">
            <span class="archive-post-date">11/06</span>
            <a class="archive-post-title" href="/2021/11/06/first_sense_of_AES_algorithm/">初识AES算法</a>
        </li>
    
        
        <li class="archive-post-item">
            <span class="archive-post-date">11/06</span>
            <a class="archive-post-title" href="/2021/11/06/Create_C_Project_with_VS2019/">使用VS 2019创建一个C语言项目</a>
        </li>
    
        
        <li class="archive-post-item">
            <span class="archive-post-date">11/03</span>
            <a class="archive-post-title" href="/2021/11/03/SpringBoot_underlying_annotation/">SpringBoot底层注解</a>
        </li>
    
        
        <li class="archive-post-item">
            <span class="archive-post-date">11/02</span>
            <a class="archive-post-title" href="/2021/11/02/SpringBoot_auto_configuration/">SpringBoot依赖管理特性</a>
        </li>
    
        
        <li class="archive-post-item">
            <span class="archive-post-date">11/01</span>
            <a class="archive-post-title" href="/2021/11/01/SpringBoot2_introduction/">SpringBoot2入门</a>
        </li>
    
        
        <li class="archive-post-item">
            <span class="archive-post-date">11/01</span>
            <a class="archive-post-title" href="/2021/11/01/SpringBoot2_data/">SpringBoot2学习资料</a>
        </li>
    
        
        <li class="archive-post-item">
            <span class="archive-post-date">11/01</span>
            <a class="archive-post-title" href="/2021/11/01/Spring_or_SpringBoot/">Spring与SpringBoot</a>
        </li>
    
        
        <li class="archive-post-item">
            <span class="archive-post-date">10/26</span>
            <a class="archive-post-title" href="/2021/10/26/hello-world/">Hello World</a>
        </li>
    
    </div>
</div>

        <div class="sidebar-panel-tags">
    <div class="sidebar-tags-name">
        
            <span class="sidebar-tag-name" data-tags="LeetCode">
                <span class="iconfont-archer">&#xe606;</span>
                LeetCode
            </span>
        
            <span class="sidebar-tag-name" data-tags="动态规划">
                <span class="iconfont-archer">&#xe606;</span>
                动态规划
            </span>
        
            <span class="sidebar-tag-name" data-tags="贪心法">
                <span class="iconfont-archer">&#xe606;</span>
                贪心法
            </span>
        
            <span class="sidebar-tag-name" data-tags="分治法">
                <span class="iconfont-archer">&#xe606;</span>
                分治法
            </span>
        
            <span class="sidebar-tag-name" data-tags="归并排序">
                <span class="iconfont-archer">&#xe606;</span>
                归并排序
            </span>
        
            <span class="sidebar-tag-name" data-tags="SpringBoot">
                <span class="iconfont-archer">&#xe606;</span>
                SpringBoot
            </span>
        
            <span class="sidebar-tag-name" data-tags="VS 2019">
                <span class="iconfont-archer">&#xe606;</span>
                VS 2019
            </span>
        
            <span class="sidebar-tag-name" data-tags="C/C++">
                <span class="iconfont-archer">&#xe606;</span>
                C/C++
            </span>
        
            <span class="sidebar-tag-name" data-tags="AES算法">
                <span class="iconfont-archer">&#xe606;</span>
                AES算法
            </span>
        
    </div>
    <div class="iconfont-archer sidebar-tags-empty">&#xe678;</div>
    <div class="tag-load-fail" style="display: none; color: #ccc; font-size: 0.6rem;">
        缺失模块，请参考主题文档进行安装配置：https://github.com/fi3ework/hexo-theme-archer#%E5%AE%89%E8%A3%85%E4%B8%BB%E9%A2%98
    </div> 
    <div class="sidebar-tags-list"></div>
</div>

        <div class="sidebar-panel-categories">
    <div class="sidebar-categories-name">
    
    </div>
    <div class="iconfont-archer sidebar-categories-empty">&#xe678;</div>
    <div class="sidebar-categories-list"></div>
</div>

    </div>
</div>

        <!-- site-meta -->
        <script>
    var siteMetaRoot = "/"
    if (siteMetaRoot === "undefined") {
        siteMetaRoot = '/'
    }
    var siteMeta = {
        url: "https://mnjic.gitee.io",
        root: siteMetaRoot,
        author: "Coder XiaoLiu"
    }
</script>

        <!-- import experimental options here -->
        <!-- Custom Font -->


        <!-- main func -->
        <script src="/scripts/main.js?v=20211217"></script>
        <!-- dark mode -->
        <script src="/scripts/dark.js?v=20211217"></script>
        <!-- fancybox -->
        <script src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js" defer></script>
        <!-- algolia -->
        
        <!-- busuanzi -->
        
            <script src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" async></script>
        
        <!-- CNZZ -->
        
        <!-- async load share.js -->
        
            <script src="/scripts/share.js?v=20211217" async></script>
        
        <!-- mermaid -->
        
    </body>
</html>
